⟸ pàgina anterior ⟸

Exercici 3 (Tasca 4).

(context-free languages, ambiguity, dyck language)

Llenguatges de Dyck

En aquest exercici considerem el llenguatge de Dyck, és a dir, el llenguatge dels parèntesis ben formats (i algunes variants). Més concretament, donat l’alfabet \Sigma=\{(,)\}, el llenguatge de Dyck \mathsf{dyck}(1) és \mathsf{dyck}(1) =\{w\in \Sigma^* \mid \text{per a tot prefix $u$ de $w$} \ \ |u|_(\geq |u|_)\land |w|_(=|w|_)\}.

De manera semblant, sigui \mathsf{dyck}(s) el llenguatge de Dyck sobre s parells de parèntesis, és a dir, el llenguatge de les seqüències equilibrades de s tipus diferents de parèntesis. Per exemple, donats els dos tipus de parèntesis (, ), i [, ], es compleix que ([])\in \mathsf{dyck}(2) i ()[]\in \mathsf{dyck}(2) però ([)]\notin \mathsf{dyck}(2).

1. Demostreu que la gramàtica S \to SS \mid (S) \mid \lambda genera exactament \mathsf{dyck}(1). És ambigua?

2. Demostreu que la gramàtica S \to (S)S \mid \lambda genera exactament \mathsf{dyck}(1). És ambigua?

3. Demostreu que la gramàtica S \to SS \mid (S) \mid [S] \mid\lambda genera exactament \mathsf{dyck}(2). És ambigua?

4. Demostreu que la gramàtica S \to (S)S \mid [S]S \mid \lambda genera exactament \mathsf{dyck}(2). És ambigua?

5. Construïu una gramàtica inambigua que generi \mathsf{dyck}(s) per a un s arbitrari.

6. Sigui \Sigma=\{(,),[,]\} i L el llenguatge de tots els mots sobre \Sigma^* que, ignorant els símbols [, ], estan ben parentitzats sobre (, ), i, similarment, ignorant els símbols (, ), estan ben parentitzats sobre [, ]. En particular, \mathsf{dyck}(2)\subseteq L, però la inclusió és estricta. Per exemple, ([)]\in L\setminus \mathsf{dyck}(2). Demostreu que L no és un llenguatge incontextual.

   Consell

   Feu servir el fet que el llenguatge \{a^nb^nc^n \mid n\in \mathbb N\} no és incontextual.

Nota

Els llenguatges de Dyck són importants perquè, en cert sentit, són els llenguatges incontextuals més difícils. En efecte, el teorema de representació Chomsky–Schützenberger estableix que un llenguatge L és incontextual si i només si L és la imatge per homomorfisme de la intersecció d’algun \mathsf{dyck}(s) amb un llenguatge regular.